//设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。 
//
// 
// push(x) -- 将元素 x 推入栈中。 
// pop() -- 删除栈顶的元素。 
// top() -- 获取栈顶元素。 
// getMin() -- 检索栈中的最小元素。 
// 
//
// 示例: 
//
// MinStack minStack = new MinStack();
//minStack.push(-2);
//minStack.push(0);
//minStack.push(-3);
//minStack.getMin();   --> 返回 -3.
//minStack.pop();
//minStack.top();      --> 返回 0.
//minStack.getMin();   --> 返回 -2.
// 
// Related Topics 栈 设计

  
package leetcode.editor.cn;
public class P155MinStack{
  public static void main(String[] args) {
      MinStack solution = new P155MinStack().new MinStack();
       //TO TEST
  }
  //leetcode submit region begin(Prohibit modification and deletion)
  class MinStack {
      private Node head;

      public void push(int x) {
          if(head == null)
              head = new Node(x, x);
          else
              head = new Node(x, Math.min(x, head.min), head);
      }

      public void pop() {
          head = head.next;
      }

      public int top() {
          return head.val;
      }

      public int getMin() {
          return head.min;
      }

      private class Node {
          int val;
          int min;
          Node next;

          private Node(int val, int min) {
              this(val, min, null);
          }

          private Node(int val, int min, Node next) {
              this.val = val;
              this.min = min;
              this.next = next;
          }
      }
  }

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(x);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */
//leetcode submit region end(Prohibit modification and deletion)

}